package com.lsa.skienna.challenge.chap9.the110902_PlayingWithWheels;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main implements Runnable{
    private static final int WHEEL_NUMBER = 4;
    private static final int CONFIGURATION_NUMBER = pow(10, WHEEL_NUMBER);
    
    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    @Override
    public void run() {
        process(System.in, System.out);
    }
    
    static void process(InputStream in, PrintStream out) {
        TaskReader taskReader = new TaskReader(in);
        try {
            Task task = null;
            while((task = taskReader.nextTask()) != null){
                out.println(solve(task));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
    
    /**
     * @param task
     * @return minimum number of button press
     */
    static int solve(Task task) {
        Queue<Configuration> queue = new LinkedList<Configuration>();
        
        int[] parentRelation = new int[CONFIGURATION_NUMBER];
        Arrays.fill(parentRelation, -1);
        boolean[] discovered = new boolean[CONFIGURATION_NUMBER];
        
        queue.add(task.startConf);
        discovered[task.startConf.number] = true;
        
        while(!queue.isEmpty()) {
            Configuration v = queue.poll();
            
            if (!task.forbiddenConfs.contains(v)) {
                if (task.targetConf.number == v.number) {
                    return calcPathEdgeCount(parentRelation, v.number);
                }
                
                List<Configuration> edgeEndpoints = calcEdgeEndpoints(v);
                for (int i = 0; i < edgeEndpoints.size(); i++) {
                    Configuration u = edgeEndpoints.get(i);
                    if (!discovered[u.number]) {
                        discovered[u.number] = true;
                        parentRelation[u.number] = v.number;
                        queue.add(u);
                    }
                }
            }
        }
        
        return -1;
    }

    public static int calcPathEdgeCount(int[] parentRelation, int number) {
        int pathEdgeCount = 0;
        while(parentRelation[number] != -1) {
            pathEdgeCount++;
            number = parentRelation[number];
        }
        
        return pathEdgeCount;
    }
    
    public static void outputInteger(PrintStream ps, int n) {
        String s = String.format("%04d", n);
        for (int i = 0; i < s.length(); i++) {
            ps.print(s.charAt(i));
            ps.print(' ');
        }
        ps.println();
    }
    
    static List<Configuration> calcEdgeEndpoints(Configuration conf){
        List<Configuration> edgeEndpoints = new ArrayList<Configuration>();
        
        for (int i = 0; i < WHEEL_NUMBER; i++) {
            for (boolean isLeft : new boolean[]{true, false}) {
                edgeEndpoints.add(conf.pressButton(i, isLeft));
            }
        }
        
        return edgeEndpoints;
    }
    
    static class TaskReader{
        private BufferedReader reader;
        private boolean isFirst;
        private int caseNumber;

        TaskReader(InputStream stream) {
            this.reader = new BufferedReader(new InputStreamReader(stream));
            this.isFirst = true;
        }
        
        Task nextTask() throws IOException {
            if (isFirst) {
                String line = reader.readLine();
                if (line == null){
                    return null;
                }
                caseNumber = Integer.parseInt(line.trim());
                isFirst = false;
            }
            
            Task task = null;
            
            if (caseNumber-- > 0) {
                String line = reader.readLine();
                if (line == null){
                    return null;
                }
                
                task = new Task();
                task.startConf = readConfiguration(reader);
                task.targetConf = readConfiguration(reader);
                Scanner scanner = new Scanner(reader.readLine());
                int noOfForbiddenConfs = scanner.nextInt();
                for (int i = 0; i < noOfForbiddenConfs; i++) {
                    task.forbiddenConfs.add(readConfiguration(reader));
                }
            }
            
            return task;
        }
        
        Configuration readConfiguration(BufferedReader reader) throws IOException{
            String line = reader.readLine();
            Scanner scanner = new Scanner(line);
            int[] numbers = new int[WHEEL_NUMBER];
            for (int i = 0; i < WHEEL_NUMBER; i++) {
                numbers[i] = scanner.nextInt();
            }
            return new Configuration(numbers);
        }
    }
    
    static class Task{
        Configuration startConf;
        Configuration targetConf;
        
        Set<Configuration> forbiddenConfs = new HashSet<Configuration>();
    }
    
    static class Configuration{
        final int[] numbers;
        final int number;

        Configuration(int[] numbers) {
            this.numbers = numbers;
            number = calcNumber();
        }
        
        Configuration pressButton(int buttonNumber, boolean isLeftOrRight ) {
            int[] numbers = this.numbers.clone();
            
            numbers[buttonNumber] += isLeftOrRight? 1 : -1;
            if (numbers[buttonNumber] == 10) {
                numbers[buttonNumber] = 0;
            }
            else if (numbers[buttonNumber] == -1) {
                numbers[buttonNumber] = 9;
            }
            
            return new Configuration(numbers);
        }
        
        int calcNumber() {
            int number = 0;
            for (int i = 0; i < WHEEL_NUMBER; i++) {
                number += pow(10, WHEEL_NUMBER - 1 - i)*numbers[i];
            }
            
            return number;
        }
        
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + Arrays.hashCode(numbers);
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Configuration other = (Configuration) obj;
            return number == other.number;
        }

        @Override
        public String toString() {
            return "<" + number + ">";
        }
    }
    
    static int pow(int num, int pow) {
        int res = 1;
        for (int i = 0; i < pow; i++) {
            res *= num; 
        }
        
        return res;
    }
}
